class Solution:
    def mySqrt(self, x: int) -> int:
        left, right = 0, x // 2 + 1
        while left < right:
            mid = (right+left+1) // 2
            if mid * mid > x:
                right = mid - 1
            elif mid * mid < x:
                left = mid
            else:
                return mid
        return right

if __name__ == '__main__':
    s = Solution()
    print(s.mySqrt(8))
    print(s.mySqrt(1))
    print(s.mySqrt(0))
    print(s.mySqrt(123324234))